package com.study.algorithm.substring;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class SlidingWindowMaximum {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 步骤1：移除不在当前窗口的索引
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // 步骤2：维护单调递减性
            while (!deque.isEmpty() && (nums[deque.peekLast()] < nums[i])) {
                deque.pollLast();
            }

            // 步骤3：将当前索引入队
            deque.offerLast(i);

            // 步骤4：记录当前窗口的最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        System.out.println("输入数组: " + Arrays.toString(nums));
        System.out.println("窗口大小: " + k);
        System.out.println("开始计算滑动窗口最大值...\n");

        int[] result = maxSlidingWindow(nums, k);

        System.out.println("\n最终结果: " + Arrays.toString(result));
    }
}